The present invention relates to a computer graphics display system and, more particularly, to a method and apparatus for performing scan conversion in a computer graphics display system.
In three-dimensional (3-D) computer graphics display systems, primitives are rendered on a display device of the computer graphics display system to produce a visual image on the display device. Each primitive is defined by X, Y and Z values of the primitive, by the normals of the vertices of the primitive, and by the colors of the vertices. Computer graphics display systems have been proposed which would utilize a Z pyramid memory element, or Z buffer, to test for primitive occlusion. For example, one such system was proposed in an article entitled xe2x80x9cHierarchical Z-Buffer Visibilityxe2x80x9d, SIGGRAPH 93, Anaheim, Calif., Aug. 1-6 1993, by Greene, et al., that would utilize a Z pyramid memory element, or Z buffer, to test for primitive occlusion.
In the system proposed by Greene et al., the Z buffer stores the Z values for a current frame of pixels in a data structure arranged as a pyramid of Z values. These Z values in the pyramid are utilized in a hierarchical tiler to test new Z values to determine whether a each primitive associated with a new Z value is occluded. If a primitive is found to be occluded, there is no need to scan convert the primitive into pixels because the occluded primitive should not be displayed on the display device. This is because, if the occluded primitive is displayed, the occluded primitive will cover another primitive which is supposed to be in front of the occluded primitive in the image being rendered on the display device.
The article by Greene, et al. discusses building the Z pyramid from the original Z buffer and using the Z pyramid to test cubes comprised of a plurality of primitives for occlusion culling. This approach makes use of the observation that the cube is hidden with respect to the Z buffer if all of its faces correspond to hidden polygons.
Prior to performing this comparison, the Z pyramid is constructed by starting with pixel-level Z values as the base of the pyramid and by comparing subgroups of adjacent Z values to determine the maximum Z value for each subgroup. The maximum Z value for that subgroup is then stored in the Z buffer for the next level up in the pyramid. For example, if 64 Z values were contained in the Z buffer when the comparison began, the next level up in the pyramid will contain 16 Z values, with each of the 16 Z values corresponding to the maximum Z value of the four pixels compared in the corresponding subgroup in the level below it.
In this next level up, the Z values of each subgroup of four adjacent Z values are compared to determine the maximum Z value for each subgroup and then this maximum Z value is stored in the Z buffer for the next level up in the pyramid. Therefore, for the next level up in the pyramid, the Z buffer will contain four Z values. These four Z values are then compared to determine the maximum Z value, which is stored in the Z buffer for the next level up in the pyramid. This last maximum Z value corresponds to the top of the pyramid.
In the computer graphics display system proposed by Greene et al., once the Z pyramid has been constructed, the Z values for the primitives making up the faces of the cubes are compared beginning at a particular level of the pyramid and working down towards the base of the pyramid. For each primitive, the minimum Z value of the primitive is tested against the levels of the pyramid in a top-to-bottom sequence. If the minimum Z value for the primitive is greater than the pyramid Z value, then the primitive is fully occluded. If all of the primitives making up the faces of the cube are occluded, the cube is occluded and can be discarded. If not, the process continues at each level of the pyramid until the cube is either fully occluded or until the process reaches the level in the Z pyramid at which a primitive is found to be at least partially visible. Once a primitive corresponding to a face of the cube is found to be at least partially visible, the entire cube is scan converted into pixels using a typical scan conversion process.
Scan conversion is a process which determines the exact pixel locations on the screen of the display device that correspond to the primitives. Scan conversion is normally performed by an edge stepper engine which steps down along the edges of a primitive until a point on the edge of the primitive is reached at which the primitive intersects a scan line, and then steps across the span corresponding to the scan line to determine the point on the opposite side of the primitive at which the scan line intersects the primitive.
One disadvantage of the typical approach to performing scan conversion is that the typical approach begins at the pixel level at a starting pixel location, which must be determined for each span by either the host central processing unit (CPU) or by the geometry accelerator of the computer graphics display system. Determining the starting pixel location and the parameters associated with the starting pixel location for each span is a mathematically intensive process. Once the starting pixel location and the parameters associated with it have been determined for a particular span, the edge stepper then steps across the primitive in the above-discussed manner.
Another disadvantage of the typical approach to scan conversion is that it results in one-dimensional locality of pixels because of the manner in which an entire span of pixels are obtained for a scan line in the x direction (i.e., horizontal) before the next span of pixels are obtained for the next scan line. This results in one-dimensional grouping of pixels, i.e., grouping in terms of the x dimension in screen space, which does not facilitate organization and storage of pixels in the frame buffer memory. In order to maximize the speed with which pixels are read out of the frame buffer memory and sent to the display monitor, it is desirable to group pixels in the frame buffer memory in groups having two-dimensional locality, i.e., in terms of the x and y dimensions in screen space.
It would be advantageous to utilize a scan conversion process which would eliminate the necessity of determining the starting pixel location for each span and thereby simplify the scan conversion process. It would also be advantageous to link the scan conversion process with the occlusion testing process performed in the hierarchical tiler in order to take advantage of the hierarchy of the Z pyramid. This would enable the occlusion testing process and the scan conversion process to be performed simultaneously in the hierarchical tiler, which could significantly increase the overall throughput of the computer graphics display system. It would also be advantageous to utilize a scan conversion process which scan converts primitives into pixels which are grouped in terms of the x and y dimensions in screen space.
Accordingly, a need exists for an improved method and apparatus for performing scan conversion. A need also exists for a scan conversion process, which is performed in a hierarchical tiler simultaneously with occlusion testing.
The present invention provides a method and apparatus for performing scan conversion in a computer graphics display system to determine pixel locations in screen space corresponding to a primitive being scan converted. Screen space corresponds to x and y coordinates of pixel locations on a display monitor of the computer graphics display system. The apparatus of the present invention comprises logic configured to convert a primitive into pixel locations in screen space, wherein each pixel location is defined by an x coordinate and by a y coordinate in screen space. Each primitive has a plurality of vertices, each of which is defined by an x coordinate and by a y coordinate in screen space.
The logic, which will be referred to hereinafter as the hierarchical tiler, subdivides the screen space into a plurality of regions, each of which comprises a plurality of pixel locations in screen space. The hierarchical tiler then determines whether a particular one of the regions is entirely outside of the primitive, entirely inside of the primitive, or partially inside of the primitive. If the hierarchical tiler determines that a particular region is entirely inside of the primitive, it converts the particular region into pixel locations in screen space. If the hierarchical tiler determines that the particular region is partially inside of the primitive, it subdivides the particular region into a plurality of sub-regions, each sub-region being comprised of a plurality of pixel locations in screen space. The hierarchical tiler then determines whether a particular one of the plurality of sub-regions is entirely outside of the primitive, entirely inside of the primitive, or partially inside of the primitive. If the hierarchical tiler determines that a particular sub-region is entirely inside of the primitive, it converts the particular sub-region into pixel locations in screen space.
The hierarchical tiler preferably only determines whether a particular region or sub-region is entirely inside of a primitive after it has determined that the particular region or sub-region is not entirely outside of the primitive. The hierarchical tiler preferably only determines whether a particular region or subregion is partially inside of a primitive after it has determined that the particular region or sub-region is not entirely inside of the primitive.
In accordance with the preferred embodiment of the present invention, the hierarchical tiler performs scan conversion in conjunction with occlusion testing. In accordance with an alternative embodiment of the present invention, the scan conversion process of the present invention is an entirely separate process which is performed separately from occlusion testing. In accordance with the preferred embodiment of the present invention, when the hierarchical tiler determines that a particular region is entirely inside of a particular primitive, it determines whether or not the particular primitive is occluded before converting the particular region into pixel locations. The particular region is only converted into pixel locations in screen space if the hierarchical tiler determines that the particular primitive is not occluded.
When the hierarchical tiler determines that a particular region is partially inside of the particular primitive, it then determines whether the particular primitive is occluded. If the hierarchical tiler determines that the particular primitive is not occluded, it subdivides the particular region found to be partially inside of the particular primitive into a plurality of sub-regions. Each sub-region is comprised of a plurality of pixel locations in screen space. The hierarchical tiler then determines whether a particular one of the sub-regions is entirely outside of the particular primitive, entirely inside of that particular primitive, or partially inside of the particular primitive.
If the hierarchical tiler determines that a particular sub-region is entirely inside of the particular primitive, it then determines whether or not the particular primitive is occluded. If the hierarchical tiler determines that the particular primitive is not occluded, it converts the particular sub-region determined to be inside of the particular primitive into pixel locations in screen space. The pixels are then sent downstream for further processing in the graphics pipeline of the computer graphics display system. If the hierarchical tiler determines that the particular sub-region is partially inside of the particular primitive, it then determines whether or not the particular primitive is occluded.
If the hierarchical tiler determines that the particular primitive is not occluded, it subdivides the particular sub-region into a plurality of smaller subregions, each of which is comprised of a plurality of pixel locations in screen space. The hierarchical tiler then determines whether a particular one of these smaller sub-regions is entirely outside of the particular primitive, entirely inside of that particular primitive, or partially inside of the particular primitive. The process continues in this manner until a region or sub-region is found to be entirely or partially contained within a primitive and has been converted into pixels or until the pixel level is reached.
These and other advantages and features of the present invention will become apparent from the following description, drawings and claims.